package leetcode.tree;

public class nodeNum {
    public static int process(Node head){
        if (head == null){
            return 0;
        }
        return bs(head,1,mostLeftLevel(head,1));
    }

    /**
     *
     * @param node 当前节点
     * @param l 左数层数
     * @param h 总层数
     * @return 以当前结点为头节点的节点数。
     */
    public static int bs(Node node,int l,int h){
        if (l == h){
            return 1;
        }
        //如果右树的层数加一和总层数相等说明左子树是个满二叉树
        if (mostLeftLevel(node.right,1+l) == h){
            //1<<(h-1):左子树总结点数+头节点
            //bs():当前节点的右子节点为头节点的子树结点总数
            return (1 << (h-1)) + bs(node.right,l+1,h);
        } else {
            //如果不想等右树一定是满二叉树
            //1<<(h-l-1):右子树的总结点数+头节点
            return (1 << (h-l-1)) +bs(node.left,l+1,h);
        }
    }

    /**
     *
     * @param node 当前节点
     * @param level 当前层数
     * @return 以node为头节点的层数
     */
    public static int mostLeftLevel(Node node,int level){
        while (node != null){
            level++;
            node = node.left;
        }
        return level-1;
    }
}
